#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ return pf.read(pid, buffer); }
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ return pf.write(pid, buffer); }

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
void BTLeafNode::incrementKeyCount()
{ char* keyCountPtr=buffer+NODE_SIZE;
	(*((int *) keyCountPtr))++;

}
void BTLeafNode::setKeyCount(int n)
{
	char* keyCountPtr=buffer+NODE_SIZE;
	(*((int *) keyCountPtr))=n;
}

int BTLeafNode::getKeyCount()
{ 
	char* keyCountPtr=buffer+NODE_SIZE;
	return (*((int *) keyCountPtr));

}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{  if (getKeyCount() >= MAX_NUM_ENTRY)  
		return RC_NODE_FULL ;
	int eid;

	if(locate ( key ,eid) == RC_NO_SUCH_RECORD )
		eid = getKeyCount();
	char* ptr= buffer + eid * ENTRY_SIZE;

	// at this point ,ptr points to the  position to insert the new recordid and key
	
	int numBytesToCopy = (getKeyCount() - eid) * ENTRY_SIZE;
	memmove (ptr+ENTRY_SIZE, ptr , numBytesToCopy);
	  
	* ( (RecordId *) ptr ) = rid;
	  
	ptr = ptr + sizeof (RecordId );
	   
	* ( (int *) ptr ) = key;
	
	incrementKeyCount();

	return 0;


}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{   //make sure the node is already full
	if (getKeyCount() < MAX_NUM_ENTRY)
		return  RC_INVALID_FILE_FORMAT;
	// make sure sibling is empty 
	if (sibling.getKeyCount() != 0 ) 
		return  RC_INVALID_FILE_FORMAT;
	
	int mid = getKeyCount() /2 ;
	
	
	int key2 ; RecordId  rid2;
	readEntry ( mid, siblingKey , rid2);
	if (key >siblingKey)
		mid++;
	// get the siblingKey 
	readEntry ( mid, siblingKey , rid2);
	
	//copy the second half of the node to the sibling

	for ( int eid = mid; eid < MAX_NUM_ENTRY; eid ++ ) 
	{
	    readEntry( eid,  key2,  rid2);
		sibling.insert (key2 ,rid2 );

	}
	setKeyCount(mid);

	//insert the node 
	if (key > siblingKey )
		sibling.insert ( key , rid);
	else insert (key ,rid );

	//set the pointers 
	sibling.setNextNodePtr ( getNextNodePtr () ) ;
	int siblingFirstKey; RecordId siblingFirstRid;
	sibling.readEntry( 0,  siblingFirstKey,  siblingFirstRid);
	siblingKey=siblingFirstKey;
	//setNextNodePtr ( siblingFirstRid.pid );
	
//	cout<<"after split !!! sibling key is  "<< siblingKey<<endl;

	return 0;
}
/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	//perform a linear search on the page
	int key; RecordId rid;

	for(int id=0 ; id < getKeyCount(); id++)
		{
			readEntry( id,  key,  rid);
			if ( key >= searchKey )
			 {eid = id; return 0;}

	     }

	eid=getKeyCount();
	return RC_NO_SUCH_RECORD;




}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{  if ( eid >= getKeyCount()  ) 
		return RC_INVALID_CURSOR;
   
  char * ptr = buffer + eid * ENTRY_SIZE;
  //ptr now points to the begining of the entry 
  
  rid = *((RecordId *) ptr );  //get the result of rid
  ptr = ptr + sizeof (RecordId);  // ptr now points to the beginning of key
  key = *((int *) ptr) ;

  return 0;

}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{  PageId * ptr ;
   ptr = (PageId * ) (buffer+ (NODE_SIZE - sizeof ( PageId )));
	return (*ptr);

}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 

	PageId * ptr;
	ptr= (PageId * ) (buffer + NODE_SIZE-sizeof(PageId)) ;
	*ptr = pid;
	return 0;

}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ return pf.read(pid, buffer); }
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ return pf.write(pid, buffer); }

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
void BTNonLeafNode::incrementKeyCount()
{ char* keyCountPtr=buffer+NODE_SIZE;
	(*((int *) keyCountPtr))++;

}
void BTNonLeafNode::setKeyCount(int n)
{
	char* keyCountPtr=buffer+NODE_SIZE;
	(*((int *) keyCountPtr))=n;
}

int BTNonLeafNode::getKeyCount()
{ 
	char* keyCountPtr=buffer+NODE_SIZE;
	return (*((int *) keyCountPtr));

}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	if (getKeyCount() >= MAX_NUM_ENTRY)  
		return RC_NODE_FULL ;
	int eid;

	if(locate ( key ,eid) == RC_NO_SUCH_RECORD )
		eid = getKeyCount();
	char* ptr= buffer + eid * ENTRY_SIZE+sizeof(PageId);

	// at this point ,ptr points to the  position where  insert the new pid and key
	
	int numBytesToCopy = (getKeyCount() - eid) * ENTRY_SIZE;
	memmove (ptr+ENTRY_SIZE, ptr , numBytesToCopy);
	  
	* ( (int *) ptr ) = key;
	  
	ptr = ptr + sizeof (key );
	   
	* ( (PageId *) ptr ) = pid;
	
	incrementKeyCount();

	return 0;


}

/*
 * Read the (key, pid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param pid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::readEntry(int eid, int& key, PageId& pid)
{  if ( eid >= getKeyCount()  ) 
		return RC_INVALID_CURSOR;
   
  char * ptr = buffer + eid * ENTRY_SIZE+sizeof(PageId);
  //ptr now points to the begining of the entry 
  
  key = *((int *) ptr );  //get the result of key
  ptr = ptr + sizeof (int);  // ptr now points to the beginning of pageid
  pid = *((PageId *) ptr) ;
  return 0;



}
/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locate(int searchKey, int& eid)
{ 
	//perform a linear search on the page
	int key; PageId pid;

	for(int id=0 ; id < getKeyCount(); id++)
		{
			readEntry( id,  key,  pid);
	//		cout<<"inside locate key is "<<key<<"search key is "<<searchKey<<endl;
			if ( key >= searchKey )
			 {eid = id; 
	//cout<<"weird ! why we never  get here"<<endl;
				return 0;}

	     }

	eid=getKeyCount();
	return RC_NO_SUCH_RECORD;




}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{	if (getKeyCount() < MAX_NUM_ENTRY)
		return  RC_INVALID_FILE_FORMAT;
    if (sibling.getKeyCount() != 0 ) 
		return  RC_INVALID_FILE_FORMAT;
	int midId= getKeyCount()/2;// cout<<"midId "<<midId;
	int eid;
	int midKeyId;
	int tempKey;
	PageId tempPid;
	locate(key , eid);
	if (eid < midId)
		midKeyId=midId-1;
	else if(eid>midId)
		midKeyId=midId;
	
	else if (midId==eid)  //the entry to insert will be the midkey
		{for(int k=midId; k<MAX_NUM_ENTRY ; k++)
			{
	           readEntry( k,  tempKey,  tempPid);
		        sibling.insert (tempKey ,tempPid);
			}
			setKeyCount(MAX_NUM_ENTRY/2);
			midKey=key;
			sibling.setFirstPid(pid);
			return 0;
		}
	//cout<<"midKeyId  is "<<midKeyId <<endl;
	//get the mid key
	readEntry(midKeyId,  midKey,  tempPid);
	
	sibling.setFirstPid(tempPid);
//	cout<<"printing content "; PrintTest();
	
	

	//cout<<"printing content "; PrintTest();
	
	for(int k=midKeyId+1; k<MAX_NUM_ENTRY ; k++)
	{
	    readEntry( k,  tempKey,  tempPid); //cout<<"starting from midKeyid+1  "<<"k "<<k<<"temp key  "<<tempKey<<"tempPid  "<<tempPid<<endl;
		sibling.insert (tempKey ,tempPid);
	}
	setKeyCount(midKeyId);
	//sibling.PrintTest();
	//cout<<key;
	if (eid < midId)
		insert(key,pid);
	else if(eid>midId)
		sibling.insert(key,pid);
	
	
	
	return 0;

	



}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{	
	int eid;
	//cout<<"god print this root"<<endl;
	//PrintTest();
	RC rc=locate(searchKey , eid);
	if(rc==RC_NO_SUCH_RECORD)
		{  //cout<<"inside locatechildptr, no such record"<<endl;
			char* ptr= buffer + getKeyCount() * ENTRY_SIZE; pid= * ((PageId*) ptr); return 0;}

	int tempKey;
	PageId tempPid;
	readEntry( eid, tempKey, tempPid);
	char* ptr= buffer + eid * ENTRY_SIZE+sizeof(PageId);
	//cout<<"inside locatechildptr deciding "<<searchKey<<"and "<<tempKey<<endl;
	if(searchKey < tempKey)
		{
			ptr = ptr - sizeof(PageId);
			pid = * ((PageId*) ptr);
	    }
	else if (searchKey == tempKey){
		pid=tempPid;
	}
	
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{	setKeyCount(0);
	setFirstPid(pid1);
	insert(key,pid2);
	return 0;
}


void BTNonLeafNode::setFirstPid(PageId pid)
{	* ((PageId* ) buffer)=pid;
}

PageId BTNonLeafNode::getFirstPid()
{  return 	(* ((PageId* ) buffer));
}
